(*
 * PdP ML
 * 
 * Francesco Cotto 
 *
 * Es.4 QuickSort polimorfo
 *
 *)


exception ValNotInRange ;;


(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *)
(* * * * * * * * * * * * * * * * Liste * * * * * * * * * * * * * * * * * * * *)
(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *)
#use "random.ml" ;;

(* genera lista random tra min e max compresi (ecco perche +1) lunga len *)
let rec genRandomList min max len =
        if len>0
        then ((int (max+1-min)) + min)::genRandomList min max (len-1)
        else [];;



let rec occorrenze min max l =
        (* conta le occorrenze di n in l *)
        let rec occorrenzeAux n l =
                match l with
                [] -> 0 | 
                x::xs -> 
                        if (n=x)
                        then (1+(occorrenzeAux n xs))
                        else occorrenzeAux n xs
        in let curr = min
        in let occ = occorrenzeAux curr l 
        in if curr<=max
        then (curr,occ)::occorrenze (curr+1) max l
        else [];;



let lengthList l =
   let rec lengthListAcc l acc = 
      match l with
         []    -> acc
        |x::xs -> lengthListAcc xs (acc + 1)
   in lengthListAcc l 0 ;;
   

(* in tempo lineare *)
let rec mergelist (lsx, ldx) =
   	match (lsx, ldx) with 
   	   ([] ,[]) -> []
   	  |(  _,[]) -> lsx 
   	  |( [], _) -> ldx
   	  |(x::xs , y::ys) -> x :: mergelist (xs, ldx) ;; 
 
  
let mergelist (lsx, ldx) = lsx @ ldx ;;


(* lista ordinata di numeri da n a m, compresi *)
let generaLista (n,m) =
   let rec generaListaStepNM ( (n,m) , list) op =   
	if (n <> m) then generaListaStepNM ((n,op m) , m::list) op
	            else m::list 
      in let op = if ( n < m ) then pred
                               else succ 
            in generaListaStepNM ( (n,m) , []) op ;;


(* int list -> str per stampare liste *)
let rec listToString l elToString = 
   match l with
      [] -> "#"
     |x::[] -> elToString x ^ " " ^  listToString [] elToString
     |x::xs -> elToString x ^ " ; " ^ listToString xs elToString;;


let expToString (a,b) = string_of_int a ^"^"^string_of_int b ;;

let expToString (a,b) = 
	match b with
	  0 -> ""
	 |1 -> string_of_int a
	 |_ -> string_of_int a ^"^"^string_of_int b ;;


let listIntToString l = listToString l string_of_int ;;

let listExpToString l = listToString l expToString ;;

let printListExp l = print_string (listExpToString l) ;;
     
let printListInt l = print_string (listIntToString l) ;;


(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *)
(* * * * * * * * * * * QuickSort Funzionale  * * * * * * * * * * * * * * * * *)
(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *)
	

(* a "prima di" b se ( pari, < ) *)
let ordinePariEtMinore a b = 
   (* o entrambi pari o entrambi dispari *)
   if ( (a + b) mod 2  =  0) then a <= b
                             (* solo uno dei due pari *)
                             else if (a mod 2 = 0) then true
                                                   else false
                                             



(* quickSort  arg1:lista  arg2:relazione d'ordine *)
let rec quickgen list ordine =

   (* partition ricorsiva: costruisce la coppia di liste maggiori e minori del
    * pivot usando la funzione ordine passata come argomento *)	                   
   let rec partition pivot list ordine = 
      match list with 
        [] -> ([],[])
       |x::xs -> let p = partition pivot xs ordine 
                    in if ordine x pivot then (x::fst p, snd p)
                                            else (fst p, x::snd p)
      in match list with 
             []       -> []
            |  x::[]  -> x::[]
            |  x::xs  -> let lp = partition x xs ordine 
                            in mergelist (      quickgen (fst lp) ordine,
                                           x :: quickgen (snd lp) ordine   ) ;;
	                   

(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *)
(* * * * * * * * * * * * * * * Main con test * * * * * * * * * * * * * * * * *)
(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *)
	                   



let mainTest =

let testQuickSort =
   let listaNonOrdinata = [45;2;1;98;4;7;6;19;24;9;18;74;71]
   and ordineStandar a b = if a <= b then true else false 
   and ordineLessicografico a b = if (string_of_int a <= string_of_int b) then true else false   
      in "\n\n Test Quick Sort"
         ^ "\n Lista da ordinare : "
         ^ listIntToString listaNonOrdinata
         ^ "\n\n\t* Relazione d'ordine (pari, <=) :\n\t  "
      	 ^ listIntToString(quickgen listaNonOrdinata ordinePariEtMinore)
      	 ^ "\n\n\t* Relazione d'ordine ( <= ) :\n\t  "
         ^ listIntToString (quickgen listaNonOrdinata ordineStandar)
         ^ "\n\n\t* Relazione d'ordine (string a <= string b) :\n\t  "
         ^ listIntToString (quickgen listaNonOrdinata ordineLessicografico)
         ^ "\n\n End Test Quick Sort\n\n" 
            
in print_string "\n(* * * * * * * * * * * * * * * Main con test * * * * * * * * * * * * * * * * *)\n";
   print_string testQuickSort ;
   ();;
   
(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *)
(* * * * * * * * * * * * * * * * * * E N D * * * * * * * * * * * * * * * * * *)
(* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *)

(* verifica sulla genRandomList e ordinamento
 *
 * occorrenze 1 2 (genRandomList 1 2 100000);;
 * 
 * quickgen (genRandomList 1 100 10) (<=) ;;
 * 
 *)
